package class4;

/**
 * 位运算
 * 问题描述:
 * 在不用 + 号的情况下,进行两个数的相加操作,
 * 思路:
 * 1. a ^ b:为无进位相加
 * 2. (a & b)<<1:为进位信息
 * 结果为:
 * 无进位相加值 + 进位信息
 * 扩展:
 * 实现 + - * / 操作
 */
public class Code02_BitOperation {
    public static void main(String[] args) {
        // 负数:取反+1,然后在进行比较
        int a = 24;
        int b = 3;

        int result = add(a, b);
        System.out.println(result);

        result = sub(a, b);
        System.out.println(result);

        result = multi(a, b);
        System.out.println(result);

        result = div(9, 4);
        System.out.println(result);

    }

    /**
     * 加法操作
     */
    private static int add(int a, int b) {
        /**
         * 第一轮
         *   1010                  1010
         * ^ 0010                & 0010
         *   1000                  0010<<1 = 0100
         *----------------------
         * 第二轮
         *   1000                  1000
         * ^ 0100                & 0100
         *   1100                  0000<<1 = 0000;
         *-------------------------
         * 循环结束
         */
        while (b != 0) { // 进位信息如果不为 0 ,则继续用进位信息进行运算
            int sum = a ^ b;    // 无进位相加
            b = (a & b) << 1; // 进位信息
            a = sum;
        }
        return a;
    }

    /**
     * 减法操作
     */
    public static int sub(int a, int b) {
        /**
         * 减法实际上是加: a + (b的取反(~) + 1操作),
         * 我们已经实现了加法操作,因此: add(~b,1),得到 b的负数,也就是 3 的负数:-3
         */
        return add(a, add(~b, 1));
    }

    /**
     * 乘法操作
     * 乘法说明:
     * 假设 a = 3 和 b = 5，我们要计算 a * b（即 3 * 5）。
     * <p>
     * 初始值：
     * a = 3 (二进制 0011)
     * b = 5 (二进制 0101)
     * res = 0
     * <p>
     * 第一轮循环：
     * b = 0101，最低位是 1（b & 1）。所以将 a = 3 加到 res：
     * res = 0 + 3 = 3
     * 然后左移 a：a = 3 << 1 = 6。
     * 无符号右移 b：b = 5 >>> 1 = 2。
     * <p>
     * 第二轮循环：
     * b = 0010，最低位是 0（b & 1）。所以不加 a 到 res。
     * 然后左移 a：a = 6 << 1 = 12。
     * 无符号右移 b：b = 2 >>> 1 = 1。
     * <p>
     * 第三轮循环：
     * b = 0001，最低位是 1（b & 1）。所以将 a = 12 加到 res：
     * res = 3 + 12 = 15
     * 然后左移 a：a = 12 << 1 = 24。
     * 无符号右移 b：b = 1 >>> 1 = 0。
     * <p>
     * 退出循环：
     * b = 0，退出循环，返回 res = 15，即 3 * 5 = 15。
     */
    public static int multi(int a, int b) {
        /**
         *      0110
         *    * 0111
         *   -----------
         *  ans  = 0110 + 01100 + 011000
         *  0111 = 0001 + 0010  + 0100
         */
        int res = 0;
        while (b != 0) {
            // 0110 & 0001
            if ((b & 1) != 0) { // 判断最低为是否==1,以此判断是否参与运算
                res = add(res, a);
            }
            a <<= 1; // a <<=1: 表示左移赋值给 0110 > 01100 > 011000
            b >>>= 1; // b>>>=1: 表示右移 0111 > 011 > 01 > 0
            // >>> 运算符用于 无符号右移，它总是用 0 填充左边的空位。
            //b >>> 1 表示将 b 的二进制位向右移一位，并在左侧补充 0。
        }
        return res;
    }

    /**
     * 除法操作
     * a/b = c ,例如 108/3 = 36
     * 说明：
     * a: 0110 1100 (108)
     * b: 0000 0011 (3)
     * 过程：
     * 步骤1：b需要左移 5位，才能移动不超过a的位置，也就是：
     * a: 0110 1100
     * - b’: 0110 0000 (b‘被左移了5位)  = 2^5
     * c’: 0010 0000
     * 步骤2：剪掉移动的位置,a还剩下 0000 1100
     * a‘: 0000 1100
     * - b’: 0000 1100 (b'被移动了2位) = 2^2;
     * c‘: 0000 0100
     * c'+c' = 0010 0000 + 0000 0100 = 0010 0100 = 36;
     */
    public static int div(int a, int b) {
        int x = isNeg(a) ? negNum(a) : a;
        int y = isNeg(b) ? negNum(b) : b;
        int res = 0;
        for (int i = 30; i >= 0; i = sub(i, 1)) {
            if ((x >> i) >= y) {
                res |= (1 << i);
                x = sub(x, y << i);
            }
        }
        // 判断符号是否一样 !=  可以用 异或 代替
        return isNeg(a) != isNeg(b) ? negNum(res) : res;
    }

    public static int negNum(int num) {
        return add(~num, 1);  // 取负数，等同于num的二进制反码加1
    }

    public static boolean isNeg(int n) {
        return n < 0;
    }
}
